package uppgift2del1;

import testSortCol.CollectionWithGet;

import datastructures.LinkedCollection;

public class SortedLinkedCollection<E extends Comparable<? super E>> extends LinkedCollection<E> implements CollectionWithGet<E>{
	
	/**
     * Adds an element to the collection.
     * The element added last will be the first element 
     * given by the iterator and the first element 
     * added will be the last given by the iterator.
     * After an element has been added, the collection
     * will be sorted from low to high.
     * 
     * @param element the object to add into the list
     * @return true if the object has been added to the list and the collection has been sorted.
     * @thro	ws NullPointerException if parameter <tt>element<tt> is null. 
     */
	@Override
	public boolean add(E e) {
    	if(size() == 0) {
    		head = new Entry( (E) e, null);
    		return true;
    	} else {
    		add(e, head, null);
    		return true;
    		
    	}
	}
	
    /**
     * Find the first occurence of an element in the collection that 
     * is equal to the argument e with respect to its natural order
     * @param e The element to compare to.
     * @return An element e' in the collection satisfying e.compareTo(e') == 0.
     * If no element is found, null is returned
     */
	@Override
	public E get(E e) {
		if(e == null) {
			throw new NullPointerException();
		}
		
		if(head != null) {
			Entry current = head;
			int i;
			while((i = current.element.compareTo(e)) < 0 && current.next != null) {
				current = current.next;
			}
			if(i == 0) {
				return current.element;
			}
		}
		return null;
	}
	
	private void add(E e2, Entry current, Entry previous) {
		if(current != null && e2.compareTo(current.element) > 0) {
			add(e2, current.next, current);
		} else {
			Entry e = new Entry((E) e2, current);
			if(previous != null) {
				previous.next = e;
			} else {
				head = e;
			}
		}
	}
}
